/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-12
 * Time: 21:19
 */
class  Node{
    public char val;
    public Node left;
    public Node right;

    public Node(char val) {
        this.val = val;
    }
}
public class TestBinaryTree {
    public Node createTree() {
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        Node H = new Node('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //前序遍历
    void preorderTraversal(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    //中序遍历
    void inorderTraversal(Node root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    //后序遍历
    void postorderTraversal(Node root) {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }

    //求节点个数
    static int size = 0;

    void getsize(Node root) {
        if (root == null) {
            return;
        }
        size++;
        getsize(root.left);
        getsize(root.right);
    }

    //求叶子节点的个数
    static int leafsize = 0;

    void getLeafSize(Node root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafsize++;
        }
        getLeafSize(root.left);
        getLeafSize(root.right);
    }

    //第k层节点的个数
    int getKLevelSize(Node root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int val = getKLevelSize(root.left, k - 1) + getKLevelSize(root.right, k - 1);
        return val;
    }

    //查找指定的值
    Node find(Node root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        Node ret = find(root.left, val);
        if (ret != null) {
            //找到了
            return ret;
        }
        ret = find(root.right, val);
        if (ret != null) {
            //找到了
            return ret;
        }
        return null;
    }

    public static void main(String[] args) {
        TestBinaryTree testBinaryTree=new TestBinaryTree();
        Node root=testBinaryTree.createTree();

        System.out.println("前序遍历：");
        testBinaryTree.preorderTraversal(root);
        System.out.println();
        System.out.println("中序遍历：");
        testBinaryTree.inorderTraversal(root);
        System.out.println();
        System.out.println("后序遍历：");
        testBinaryTree.postorderTraversal(root);
        System.out.println();
        System.out.println("求节点个数：");
       testBinaryTree.getsize(root);
       System.out.println(testBinaryTree.size);
        System.out.println("求叶子节点个数：");
       testBinaryTree.getLeafSize(root);
       System.out.println(testBinaryTree.leafsize);
        System.out.println("第k层节点的个数：");
       System.out.println(testBinaryTree.getKLevelSize(root,3));
        System.out.println("查找指定的值：");
        System.out.println(testBinaryTree.find(root,'D'));
    }

}
